Information storage systems are known in which the information to be stored is identified by a word (sometimes referred to as a keyword) which may be a plain language word or a code word derived from the information to be stored. Generally, the information to be stored may be identified by a plurality of such words and, in order to enable the information, once stored, to be retrieved, it is identified by that plurality of words together or by each word separately and hence stored in a corresponding number of locations in the memory.
For example, if an item of information X.sub.1 is identified by a number of key-words, say K.sub.1 - K.sub.5, then the information could be addressed to the memory store by the keywords taken together, i.e., K.sub.1, K.sub.2, K.sub.3, K.sub.4, K.sub.5 /X.sub.1. However, in order to obtain maximum efficiency of recall of the stored information, the information should be stored under each of all possible combinations available with the number of individual keywords used (i.e., N- where N is the number of keywords in the set). In this case, this would mean entering a total of 5- .times. 5 keywords or approximately 5- .times. 5 .times. 8 characters = 4,800 characters per item of information (8 being an assumed number of characters per keyword).
Alternatively, an item of information may be identified by each of the plurality of keywords separately. In this case, the information would be addressed to the memory store as K.sub.1 /X.sub.1 ; K.sub.2 /X.sub.1 ; K.sub.3 /X.sub.1 ; K.sub.4 /X.sub.1 ; K.sub.5 /X.sub.1. In the course of time, each store location would accommodate numerous items of information. Thus, for example, the store location identified by keyword K.sub.1 may contain information items X.sub.1, X.sub.2, X.sub.7, X.sub.103, X.sub.205 etc. However, frequently recurring keywords will direct a large number of items of information to the corresponding store location whereas uncommon keywords will direct only a few items of information to the corresponding store location. This results in three distinct disadvantages:
a. each storage location should be designed to accommodate the maximum number of items of information envisaged for any of the keywords for optimum efficiency,
b. as information retrieval may take place by reading the information stored at each location identified by each one of a number of keywords related to the information to be retrieved and selecting the items of information common to each location, it will be apparent that long strips of items of information may have to be compared, and
c. the available storage capacity must be M times that referred to at a. above where M is the maximum number of keywords.
As mentioned above, in the known information storage systems referred to, each storage location is identified by a single keyword, e.g., K.sub.1 - K.sub.5 and the same item of information may be stored in each of the storage locations identified by the keywords K.sub.1 - K.sub.5.
It is known to provide compound memories which are composed of random access arrays in combination with content addressable arrays, the latter being frequently called associative arrays. Associative arrays formed into associative memories have been employed for the purpose of relating arbitrary symbolic identifiers of information such as K.sub.1 - K.sub.5, hereinafter referred to as "effective addresses" to corresponding physical memory locations. The associative memory compares the effective address with the effective addresses in its memory and, if an associative comparison (called a match) is found, reads out the actual address of the information block within the random access memory and accesses the addressed information block in the random access array so as to read or write information out of it into that block. Such a compound memory is disclosed in U.S. Pat. No. 3,685,020 to Robert M. Meade dated Aug. 15, 1972, in which is disclosed a compound memory system in which a random access array includes an associative array as part of its accessing means. There is further disclosed a nested configuration of compound memories in which the effective address is transmitted to the lowest order compound memory but held available on buses for each of the higher order compound memories. If no match is found for the effective address in the lowest order compound memory, a gating signal is generated to gate the effective address to the next higher order compound memory and this continues up the nest until a match is found and the address identified. If no match is found, an error signal is generated.
Although U.S. Pat. No. 3,685,020 discloses how an address may be tested up a nest of compound memories to find a match for the effective address, it is only concerned with identifying the actual address of the information block within the random access array in the compound memory and an information storage system embodying such compound and multilevel memories suffers from the three distinct disadvantages identified above.
The serial testing of an address is also known from U.S. Pat. No. 3,806,882 to Alan Bothwell Clarke dated Apr. 23, 1974 which is concerned with security for computer systems in which an operator is provided with a key containing identification data and which, when plugged into a computer system is compared with corresponding stored data and if found to match causes a signal to be generated to enable the operator to have access to information stored in the system and, if found not to match, causes an alarm signal to be generated. As the stored information may be classified in fractions of information of decreasing importance, an operator is issued with a key containing identification data corresponding to the level of importance of the information to which the operator is authorised for access and, when the key is plugged into the system, the identification data is compared with the data stored in one computer key storage unit and if a mis-match is found is referred to another comparator and so on until the level of authorised information is identified and made available. If no match is found, an alarm signal is generated.
Both U.S. Pat. Nos. 3,685,020 and 3,806,882 effectively disclose information storage systems in which data representing an address or a key is tested in a comparator for a match with stored data and in the event of a mis-match is passed on to a succeeding comparator until a match is found and the address identified. The matching comparator effectively generates a yes signal in the event of a match to initiate a subsequent operation or a no signal in the event of a mis-match which is used to pass the address to the succeeding comparator. Neither U.S. Pat. Specification is, however, concerned with identifying within the address data a series of words occurring in a predetermined sequence, a separate comparator being associated with each word position in the sequence and being operable to prevent further reading of the address data when the words do not appear in the predetermined sequence.
It is an object of the present invention to provide an improved information storage system in which the three distinct disadvantages referred to above are materially reduced.
It is a further object of the invention to provide an improved storage system in which each item of information to be stored is identified by two keywords (referred to as keyword pairs) the two keywords in a pair being separated by a spacer signal (considered as a word) and a keyword pair being followed by a terminal signal (considered as a word) identifying the end of a keyword pair whereby each storage location is identified by a keyword pair and the capacity of each storage location can be materially reduced and information retrieval time is also materially reduced.